package com.mlh.linkedlist;

// 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
// 不允许修改 链表
import java.util.HashSet;
import java.util.Set;

public class 环形链表2 {
    //想法1 直接加入set 第一个重复的就是入环点
    public ListNode method1(ListNode head) {
        //处理掉只有一种节点的情况
        if(head==null||head.next==null){
            return null;
        }
        Set<ListNode>set=new HashSet<>();
        ListNode pre=head;
        while (!set.contains(pre)){
            set.add(pre);
            pre=pre.next;
            if(pre==null){
                return null;
            }
        }
        return pre;
    }

    //看题解的  快慢指针  数学化证明 不懂看力扣题解
    public ListNode method2(ListNode head) {
        //处理掉只有一种节点的情况
        if(head==null||head.next==null){
            return null;
        }
        //循环不变量原则  到head就认为是走了一步了
        ListNode fast=head.next;
        ListNode slow=head;
        while (fast!=slow){
            if(fast==null||fast.next==null){
                return null;
            }
            fast=fast.next.next;
            slow=slow.next;
        }
        //fast到head就认为是走了一步了 因此slow=slow.next;
        // 接下来两者都不断next 直到两者相遇就是入环点
        fast=head;
        slow=slow.next;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

    public ListNode practice(ListNode head) {
        if(head==null||head.next==null){
            return null;
        }
        ListNode slow=head,fast=head.next;
        while(fast!=null&&fast.next!=null){
            if(fast==slow){
                //这里是背下来的，要理解的话看数学化证明
                fast=head;
                slow=slow.next;
                while(fast!=slow){
                    fast=fast.next;
                    slow=slow.next;
                }
                return fast;
            }
            fast=fast.next.next;
            slow=slow.next;
        }
        return null;
    }
    public ListNode practice2(ListNode head){
        if(head==null){
            return null;
        }
        ListNode slow=head,fast=head.next;
        while(slow!=fast){
            if(fast==null||fast.next==null){
                return null;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        slow=slow.next;
        while(head!=slow){
            head=head.next;
            slow=slow.next;
        }
        return head;
    }

}
